Computerized systems commonly include caches to provide efficient access to stored data. With a typical cache, selected data stored on slower media with higher capacity are loaded onto faster media with lower capacity. For example, data stored on a disk may be pre-fetched and brought into a portion of memory (a cache), where the data may be accessed quickly and efficiently by running programs.
Caches are typically operated at or near their full data capacity. Once a cache becomes full, new data cannot be added to the cache, e.g., in response to a pre-fetch operation, until other data are removed. Various protocols for removing data from a cache, i.e., “data replacement protocols,” are known in the art, and include, for example, least recently used (LRU), first in first out (FIFO), random replacement, and relative distance to logical block address (LBA).
Because a cache stores much less data than the media it supports, access by running programs to desired data in the cache sometimes results in the desired data being found in the cache (a “cache hit”) but sometimes results in the desired data being absent from the cache (a “cache miss”).